package LimitedTimeGame.Day_0302;

/**
 * @author zxc
 * @date 2023/03/03 08:42
 **/

import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * 题目 ：滑动窗口的最大值
 * 题目详述 ：
 * 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k个数字。
 * 滑动窗口每次只向右移动一位。
 * 返回 滑动窗口中的最大值 。
 *
 * 提示：
 * 1 <= nums.length <= 10^5
 * -10^4 <= nums[i] <= 10^4
 * 1 <= k <= nums.length
 *
 */
public class MaxSlidingWindow02 {
    public static void main(String[] args) {
        System.out.println(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3));
    }
    /**
     * 思路 ：
     * ===》
     *  即，使用双端队列维护 其中元素单调递减 && 所存储的数组下标单调递增的队列;
     *  ===》（单调队列的方法;）
     * （1）首先，初始化队列，来获取 数组下标单调递增 && 数组元素单调递减;
     * （2）其次，滑动窗口右移（新增元素），即 与队尾元素进行比较，
     *  若是大于等于该队尾元素的话，则选择弹出当前队尾元素 && 将新增元素加入到队尾中;
     * （3）然后，需要判断当前队列的队首元素是否在滑动窗口的范围内，
     *  若是不在滑动窗口的范围内的话，则需要将队首元素弹出，直至队首元素在滑动窗口内;
     * （4）最后，使用result结果数组来保存每次滑动窗口中的最大值
     *
     * ===》
     * 总结 ：
     * 在 i < j && nums[i] <= nums[j]的情况下，若是i，j两个元素在同一个滑动窗口内，
     * 则由于nums[j]的存在，所以nums[i]必然不可能是当前滑动窗口的最大值;
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        // 使用单调队列，来存储符合条件的元素
        Deque<Integer> deque = new LinkedList<>();
        //1.初始化
        for(int i = 0 ; i < k ; i++){
            // （1）若是该队列为空 || 该队列不满足单调递减，则需要将 当前元素与队尾元素进行比较，
            // 若是当前元素 >= 队尾元素的话，则需要将该队尾元素直接弹出;
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
                deque.pollLast();
            }
            // （2）队列中加入，该元素;
            deque.offerLast(i);
        }
        // 2.定义结果数组 && 将result[0]置为初始化单调递减队列的队首元素;
        int[] result = new int[len - k + 1];
        result[0] = nums[deque.peekFirst()];

        // 3.滑动窗口右移，直至遍历完nums数组
        for(int i = k ; i < len ; i++){
            // （1）若是该队列为空 || 该队列不满足单调递减，则需要将 当前元素与队尾元素进行比较，
            // 若是当前元素 >= 队尾元素的话，则需要将该队尾元素直接弹出;
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
                deque.pollLast();
            }
            // （2）队列中加入该元素;
            deque.offerLast(i);
            // （3）当前队首元素是否在滑动窗口范围内
            // 若是当前队首元素不在滑动窗口范围内的话，则新增将其弹出队列，直至队首元素是处于滑动窗口范围内;
            while(deque.peekFirst() <= i - k){
                deque.pollFirst();
            }
            result[i - k + 1] = nums[deque.peekFirst()];
        }
        return result;
    }
}
